The present invention generally relates to methods and systems for writing and reading coded data, and more particularly to a method and a system for writing and reading coded data which are coded by the orthogonal transform coding so that an image can be restored progressively or sequentially.
The information quantity of the image data is considerably large compared to that of the numerical data. Hence, especially when storing and transmitting the image data of a gray scale image or a color image at a high speed and with a high quality, it is necessary to code the tone of each pixel with a high efficiency.
When making a data base search, it is desirable that the image is reproduced with a picture quality which improves progressively from a rough image to a fine image so that the user can generally recognize the image from an early stage of the data base search. By taking this measure, it is possible to efficiently determine whether the displayed image is a required data or an unwanted data.
On the other hand, when outputting the image on a hard copy apparatus such as a printer, it is necessary to restore the image sequentially from the top left to the bottom right of the image.
As a highly efficient method of compressing the image data, there is the adaptive discrete cosine transform (hereinafter simply referred to as an ADCT). According to the ADCT, the image is divided into blocks of 8.times.8 pixels, and an image signal of each block is transformed into coefficients of a spatial frequency distribution using the two-dimensional discrete cosine transform (hereinafter simply referred to as a DCT). The coefficients of the spatial frequency distribution are quantized at a threshold value adapted for the human eye, and the obtained quantization coefficients are coded by use of a Huffman code table.
Next, a description will be given of the ADCT by referring to FIGS. 1 through 6. For example, an image is divided into blocks of 8.times.8 pixels and each pixel is described in 256 gradation levels "0" through "255". When the pixels of one block have the gradation levels shown in FIG. 1, DCT coefficients shown in FIG. 2 are obtained by transforming the image data shown in FIG. 1 into coefficients of the spatial frequency distribution using the DCT. When the DCT coefficients shown in FIG. 2 are divided by respective threshold values shown in FIG. 3 and those values which have absolute values less than the corresponding threshold values are regarded as zero, quantization coefficients shown in FIG. 4 are obtained. The quantization coefficients shown in FIG. 4 are transformed using the Huffman code, for example, so as to obtain coded data for each block of the image.
FIG. 5 shows a coding circuit which employs the ADCT. An input image is divided into the blocks of 8.times.8 pixels as shown in FIG. 1, and an input image signal which is related to the blocks is supplied to a DCT part 141 via an input terminal 140. The numbers shown in FIG. 1 indicate the gradation levels of each pixel within the block. The DCT part 141 subjects the input image signal to an orthogonal transform in conformance with the DCT according to the following formula (1), where F.sub.j denotes the DCT coefficient and f.sub.i denotes the input image signal. Hence, coefficients of the spatial frequency distribution, that is, the DCT coefficients shown in FIG. 2, are obtained from the DCT part 141. ##EQU1##
The DCT coefficients from the DCT part 141 are supplied to a linear quantization part 142. The linear quantization part 142 refers to a quantization matrix 143 which includes a table of threshold values shown in FIG. 3 which are determined by a visual experimentation, and makes a linear quantization by dividing the DCT coefficients of the pixels by the corresponding threshold values. As a result, those DCT coefficients having absolute values less than the corresponding threshold values are regarded as zero, and quantization coefficients having values for only the DC components and small AC components are generated as shown in FIG. 4. In FIG. 4, the fractions are omitted. The DC component refers to a component (0, 0) in the x and y directions in FIG. 4.
The quantization coefficients which are arranged two-dimensionally as shown in FIG. 4 are scanned in a zigzag manner with a scanning sequence shown in FIG. 6 so that the data become arranged one-dimensionally. The one-dimensionally arranged data are supplied to a variable length coding part 144. With regard to the DC components, the variable length coding part 144 subjects a difference between a first DC component of each block and a DC component of a previous block to a variable length coding. In addition, with regard to the AC components, the variable length coding part 144 subjects a run length of a value of an invalid coefficient (zero coefficient) to a value of a significant coefficient (non-zero coefficient) to a variable length coding. The DC and AC components are coded using a code table 145 which includes a Huffman code table which is made based on statistics of each image. Coded data which is obtained from the variable length coding part 144 is stored in a code data storage part 146.
On the other hand, the coded data is restored into the image according to the following method. First, when sequentially restoring the image on the printer, for example, a process is carried out in a reverse sequence in FIG. 5. That is, the coded data of the variable length coding is returned to the one-dimensionally arranged quantization coefficients by referring to the Huffman code table. Then, a reference is made to the scanning sequence shown in FIG. 6 to return the one-dimensionally arranged quantization coefficients to the two-dimensionally arranged quantization coefficients shown in FIG. 4. The threshold values shown in FIG. 3 are multiplied to the two-dimensionally arranged quantization coefficients to obtain the DCT coefficients shown in FIG. 2. The original image is successively restored in blocks by carrying out a reverse DCT on the DCT coefficients.
On the other hand, when progressively restoring the original image, the image is progressively restored in a sequence of stages (or bands) "1", "2", "3", . . . as shown in FIG. 7. FIG. 7 shows a case where the restoration is made in four stages, that is, the stages "1" through "4". In this case, the number of coded data which are to be restored in each stage per block is designated in advance. The designated number of coded data are restored into the quantization coefficients, and the quantization coefficients are divided within the block into a number of stages (bands) from a low frequency range. The quantization coefficients which are divided in each stage and restored and the quantization coefficients which are restored in the previous stage are combined, and the quantization coefficients which are not received are all set to zero to make up one block. The reverse DCT is carried out progressively in this manner to restore the original image.
In the case shown in FIG. 7, one coded data is read out from each block in the stage "1". In terms of the coded data sequence, the coded data is read out from a first coded data sequence D1, that is, the coded data is read out from only the scanning sequence number "1" of each block shown in FIG. 6. The read out coded data is restored back into the DCT coefficients by being subjected to the reverse DCT. In other words, only the DC components are restored in the stage "1" because the coded data is read out from only the coded data sequence D1 of each block.
In the stage "2", four coded data are read out. The coded data are read out from coded data sequences R0, I2,1,1, R0 and I2,1,2. In FIG. 7, Dm denotes the coded data of the difference value of the DC component of the mth block, Il,m,n denotes the coded data of the value of the nth significant coefficient of the mth block in the 1th stage (restoration stage "1"), Rk denotes the coded data which indicates that the run length of the invalid coefficient of the AC component is k, and Reob denotes the coded data which indicates that the end of the block ends with the run of the invalid coefficient.
Accordingly, the coded data (from the scanning sequence number "2" in FIG. 6) with respect to the first coefficient of the first block which has a run length "0" from the coded data sequence D1 which corresponds to the DC component and the coded data (from the scanning sequence number "3" in FIG. 6) with respect to the second coefficient of the first block which has the run length "0" from the coded data sequence D1 are read out in the stage "2". The read out coded data are restored back into the quantization coefficients by being subjected to the reverse DCT.
In the stage "3", the coded data are similarly read out from the scanning sequence numbers "4" and "5" in FIG. 6 and restored back into the quantization coefficients by being subjected to the reverse DCT.
In the stage "4", the coded data are similarly read out from the scanning sequence numbers "6" and "7" in FIG. 6 and restored back into the quantization coefficients by being subjected to the reverse DCT.
When carrying out the progressive restoration of the original image, it is possible to restore a rough image in the initial stage because the quantization coefficients in the initial stage mainly consist of low-frequency components. On the other hand, a more fine image is restored in the latter stage because the quantization coefficients in the latter stage mainly consist of high-frequency components. Hence, when making a product selection, for example, it is possible to make a rough selection in the initial stage and distinguish the unwanted products at an early stage.
A method of storing the coded data for both the sequential and progressive restoration is proposed in Miura et al., "A Study on CODEC for Still Images with Sequential/Progressive Build Up", National Conference of Electronics and Information Communication Society, Fall 1988. According to this proposed method, the image is divided into blocks of 8.times.8 pixels, and the image signal of each block is transformed into coefficients of the spatial frequency distribution in conformance with the DCT. The coefficients are quantized using threshold values which are adapted to the human eye, and the quantization coefficients are scanned in a zigzag manner as shown in FIG. 6 from the low-frequency components to the high-frequency components. With regard to DC components, a difference between the DC components of each block and a previous block is coded. On the other hand, with regard to the AC components, a run length of an invalid coefficient which is zero to a significant coefficient which is not zero is coded for each block. The above described coding process is carried out for all of the blocks of the image. Within each block, the quantized DCT coefficients which are subjected to the variable length coding form a single continuous code data sequence, and such a process is carried out with respect to all of the successive blocks. The coded data thus obtained and corresponding to the image are stored in a coded data storage part. In other words, the coding takes place in the coding circuit shown in FIG. 5 and is stored in the coded data storage part 146.
FIG. 8 shows an example of coded data sequences having the file format. In FIG. 8, the same designations are used as in FIG. 7.
When restoring the original from such coded data, a coded data reading circuit shown in FIG. 9 is used. The coded data reading circuit comprises a variable length restoration part 151, a restoration table 152, a coefficient extraction part 153, a coefficient storage part 154, a variable length coding part 155 and a code table 156. A coded data table 150 corresponds to the coded data table 146 shown in FIG. 5. The coded data reading circuit 151 reads out the variable length coded data from the coded data table 150 and carries out an image restoring process.
First, when sequentially restoring the original image, the coded data are successively read out in blocks from the coded data table 150. The original image is successively restored in blocks in a reverse sequence to the above and is supplied to a restoration circuit (not shown) via a path A and an output terminal T0.
On the other hand, when progressively restoring the original image, the storage location of the data corresponding to D1, D2, . . . which are necessary in the restoration stage "1" for the progressive restoration and the storage location of the data related to the next scanning sequence which are required in the restoration stage "2" are not known, because the coded data sequences of each block stored in the coded data storage part 150 are variable length. For this reason, the data corresponding to the image must once be restored to the quantization coefficients shown in FIG. 4, and a process must then be carried out to extract D1 which is required in the restoration stage "1" from each block and next extract the quantization coefficients of the scanning sequence which are required in the restoration stage "2".
Thus, the coded data sequences of the first, second, . . . blocks are read out from the coded data storage part 150 for one image as shown in FIG. 8 and supplied to the variable length restoration part 151. The variable length restoration part 151 refers to the restoration table 152 and restores the quantization coefficients shown in FIG. 4. The restoration table 152 stores a table which is in reverse to the Huffman code table. The coefficient extraction part 153 stores in the coefficient storage part 154 the quantization coefficients in blocks of each image. In order to carry out the progressive image restoration, the coefficient extraction part 153 thereafter extracts the designated number of quantization coefficients from the coefficient storage part 154 in blocks so as to carry out the variable length coding. The number of quantization coefficients is designated depending on the restoration stage shown in FIG. 7. As a result, the significant coefficients and the run length of the invalid coefficients to each significant coefficient are supplied to the variable length coding part 155. The variable length coding part 155 carries out a variable length coding to obtain coded data of the significant coefficients and the run lengths of the invalid coefficients which are received using the code table 156 which includes the Huffman code table. The number of coded data designated in the restoration stage are supplied to the restoration circuit via the output terminal T0.
Accordingly, in order to carry out the progressive image restoration according to the conventional method, the quantization coefficients which are restored from the coded data amounting to one image must be coded again into the coded data based on the variable length coding. For this reason, there is a problem in that a complex processing sequence must be carried out to extract the coded data corresponding to each restoration stage from the quantization coefficients which are stored in the coefficient storage part 154.